class Solution(object):
    #动态规划, dp[i] = min(dp[i+1:i+nums[i]+1]) + 1
    def jump_dp(self, nums):
        n = len(nums)
        jump_list = []
        for i in range(n):
            jump_list.append(n)

        jump_list[n - 1] = 0
        for i in range(n - 2, -1, -1):
            step = nums[i]
            if step == 0:
                continue
            else:
                jump_list[i] = min(jump_list[i + 1 : i + step + 1]) + 1
        return jump_list

    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        jump_list = self.jump_dp(nums)
        return jump_list[0]
